import java.util.ArrayList;
import java.util.List;

class Solution {
    List<String> ret;
    StringBuilder path;
    int n = 0;
    List<Integer> list;
    public List<String> letterCasePermutation(String s) {
        ret = new ArrayList<>();
        path = new StringBuilder(s);
        n = s.length();
        list = new ArrayList<>();
        int index = 0;
        for(int i = 0; i < n; i++){
            char c = s.charAt(i);
            if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')){
                list.add(i);
            }
        }

        dfs(s, 0);
        return ret;
    }
    public void dfs(String s, int pos){
        if(pos == list.size()){
            ret.add(path.toString());
            return;
        }
        int index = list.get(pos);
        char c = s.charAt(index);
        if(c >= 'a' && c <= 'z'){
            // 搜索决策树左子树
            dfs(s, pos + 1);

            // 搜索决策树右子树
            char tmp = (char)(c - 32);
            path.deleteCharAt(index);
            path.insert(index, tmp);
            dfs(s, pos + 1);
            // 回溯
            path.deleteCharAt(index);
            path.insert(index, c);
        }
        if(c >= 'A' && c <= 'Z'){
            // 搜索决策树左子树
            dfs(s, pos + 1);

            // 搜索决策树右子树
            char tmp = (char)(c + 32);
            path.deleteCharAt(index);
            path.insert(index, tmp);
            dfs(s, pos + 1);
            // 回溯
            path.deleteCharAt(index);
            path.insert(index, c);
        }
    }
}